class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        lower = 0
        upper = len(nums) - 1
        while True:
            mid = (lower + upper) / 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                lower = mid + 1
            elif nums[mid] > target:
                upper = mid - 1
            if lower > upper:
                return lower

s = Solution()
r = s.searchInsert([1, 3, 5, 6], 0)
print(r)
